11338 - Minefield/11338.2.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <queue>
   4 #include <map>
   5 #include <cmath>
   6 #include <sstream>
   7 #include <functional>
   8
   9 using namespace std;
  10
  11 const double infinity = 1E20;
  12
  13 struct point{
  14   double x, y;
  15   point(double X, double Y){ x = X; y = Y;}
  16 };
  17
  18 map< point, double > dist;
  19
  20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
  21 bool operator !=(const point &a, const point &b){ return !(a == b);}
  22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
  23 //bool operator <(point a, point b){ return (a.dist > b.dist);}
  24 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
  25
  26
  27
  28 bool heapCmp(const point &a,const point &b){
  29   return (dist[a] > dist[b]);
  30 }
  31
  32
  33 struct heapCompare : public binary_function<point, point, bool>
  34 {
  35   bool operator()(const point &x, const point &y) const
  36   { return dist[x] > dist[y]; }
  37 };
  38
  39
  40 struct grafo{
  41   //contiene todos los nodos sueltos
  42   vector<point> nodos;
  43   //contiene un vector con todos los vecinos para el punto point
  44   map< point, vector<point> > vecinos;
  45
  46   void insert(point a){
  47     if (vecinos.count(a)) return;
  48     nodos.push_back(a);
  49     if (vecinos.size() == 0){
  50       vector<point> v;
  51       vecinos.insert(make_pair(a, v));
  52     }
  53
  54     //printf("vecinos.begin() apunta a (%f,%f)\n", (*vecinos.begin()).first.x, (*vecinos.begin()).first.y);
  55
  56     map< point, vector<point> >::iterator lower, upper;
  57     lower = vecinos.lower_bound(point(a.x-1.5, a.y-1.5));
  58     //if (lower == vecinos.begin()) printf("Lower == vecinos.begin() que apunta a (%f,%f)\n", (*vecinos.begin()).first.x, (*vecinos.begin()).first.y);
  59     //if (lower == vecinos.end()) printf("Lower == vecinos.end()\n");
  60
  61     if (lower != vecinos.begin()) --lower;
  62     upper = vecinos.upper_bound(point(a.x+1.5, a.y+1.5));
  63
  64     printf("Todos los vecinos de (%f,%f) deben estar entre: (%f,%f) y (%f,%f)\n", a.x, a.y,
  65            (*lower).first.x, (*lower).first.y, (*upper).first.x, (*upper).first.y);
  66
  67
  68
  69     map< point, vector<point> >::iterator it;
  70     for (it=lower; it != upper; ++it){
  71       //Insertarlo como vecino en los nodos diferentes a el mismo
  72       if ((*it).first != a){
  73         vector<point> adj = vecinos[(*it).first];
  74         //Asegurarse de no insertar un vecino repetido
  75         if (distancia(a, (*it).first) <= 1.5){
  76           //printf("Insertando (%f,%f) como vecino de (%f,%f).\n", a.x, a.y, nodos[i].x, nodos[i].y);
  77           vecinos[(*it).first].push_back(a);
  78           vecinos[a].push_back((*it).first);
  79         }
  80       }
  81     }
  82   }
  83
  84   void initialize(){
  85     dist.clear();
  86     for (int i=0; i<nodos.size(); ++i){
  87       dist[nodos[i]] = infinity;
  88       if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
  89         dist[nodos[i]] = 0.00;
  90       }
  91     }
  92   }
  93
  94   /*void relax(point u, point v){
  95     if (dist[v] > dist[u] + distancia(u, v)){
  96       dist[v] = dist[u] + distancia(u, v);
  97     }
  98     }*/
  99
 100   void dijkstra(const double &maxPath, const point &finalPoint){
 101     initialize();
 102
 103
 104     priority_queue<point, vector<point>, heapCompare > q;
 105     q.push(point(0.0, 0.0));
 106
 107     while (!q.empty()){
 108
 109       point u = q.top();
 110       q.pop();
 111
 112       if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
 113         for (int i=0; i<vecinos[u].size(); ++i){
 114           point v = vecinos[u][i];
 115           //printf("  Comparando (%f,%f) con (%f,%f) que estan a %f\n", u.x, u.y, v.x, v.y, distancia(u,v));
 116           //printf(" dist[u] es %f, dist[v] es %f\n", dist[u], dist[v]);
 117           if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
 118             //printf("  Actualizando la distancia de v = (%f,%f)\n", v.x, v.y);
 119             dist[vecinos[u][i]] = dist[u] + distancia(u, v);
 120             //printf("  Nueva distancia de v: %f\n", dist[v]);
 121             q.push(v);
 122           }
 123         }
 124       }
 125     }
 126   }
 127
 128   void printMap(){
 129     printf("Voy a imprimir los elementos del mapa en orden.\n");
 130     map< point, vector<point> >::iterator i;// = vecinos.begin();
 131     for (i = vecinos.begin(); i != vecinos.end(); ++i){
 132       printf("  (%f,%f)\n", (*i).first.x, (*i).first.y);
 133     }
 134
 135   }
 136
 137 };
 138
 139
 140
 141 int main(){
 142   while (true){
 143
 144     string s;
 145     for (s = ""; s == ""; getline(cin, s));
 146     if (s == "*") break;
 147
 148
 149     grafo g;
 150
 151     stringstream line;
 152     line << s;
 153
 154     int w,h;
 155     line >> w >> h;
 156     g.insert(point(0.00, 0.00));
 157     g.insert(point((double)w, (double)h));
 158     int noPuntos;
 159     cin >> noPuntos;
 160     for (int i=0; i<noPuntos; ++i){
 161       double x,y;
 162       cin >> x >> y;
 163       g.insert(point(x,y));
 164     }
 165
 166
 167     cout << "Termine de insertar todos los nodos.\n";
 168
 169     g.printMap();
 170
 171
 172     double maximoCamino;
 173     cin >> maximoCamino;
 174
 175     /*printf("Voy a imprimir el grafo de %d nodos:\n", g.nodos.size());
 176     for (int i=0; i<g.nodos.size(); ++i){
 177       printf("Estos son los vecinos de (%f,%f):\n", g.nodos[i].x, g.nodos[i].y);
 178       for (int j=0; j<g.vecinos[g.nodos[i]].size(); ++j){
 179         printf("  (%f,%f)\n", g.vecinos[g.nodos[i]][j].x, g.vecinos[g.nodos[i]][j].y);
 180       }
 181       }*/
 182
 183     g.dijkstra(maximoCamino, point((double)w, (double)h));
 184     //printf("La distancia minima hasta (%d,%d) es %f.\n", w,h,dist[point((double)w, (double)h)]);
 185     if (dist[point((double)w, (double)h)] <= maximoCamino){
 186       printf("I am lucky!\n");
 187     }else{
 188       printf("Boom!\n");
 189     }
 190
 191   }
 192   return 0;
 193 }